1. Field of the Invention
The present application relates to, inter alia, methods for peer-to-peer network and information discovery systems and methods. The entire disclosures of each of the following co-pending provisional patent applications of the present assignees are incorporated herein by reference: (1) U.S. Provisional Patent Application Ser. No. 60/625,106 entitled Network Discovery Mechanisms filed on Nov. 5, 2004; (2) U.S. Provisional Patent Application Ser. No. 60/593,377 entitled Network Discovery Mechanisms filed on Jan. 9, 2005; and (3) U.S. Provisional Patent Application Ser. No. 60/670,655 entitled Network Discovery Mechanisms filed on Apr. 13, 2005.
2. Background Discussion
General Background Discussion:                Networks and Internet Protocol        
There are many types of computer networks, with the Internet having the most notoriety. The Internet is a worldwide network of computer networks. Today, the Internet is a public and self-sustaining network that is available to many millions of users. The Internet uses a set of communication protocols called TCP/IP (i.e., Transmission Control Protocol/Internet Protocol) to connect hosts. The Internet has a communications infrastructure known as the Internet backbone. Access to the Internet backbone is largely controlled by Internet Service Providers (ISPs) that resell access to corporations and individuals.
With respect to IP (Internet Protocol), this is a protocol by which data can be sent from one device (e.g., a phone, a PDA [Personal Digital Assistant], a computer, etc.) to another device on a network. There are a variety of versions of IP today, including, e.g., IPv4, IPv6, etc. Each host device on the network has at least one IP address that identifies the host device's point of attachment to the IP networks.
IP is a connectionless protocol. The connection between end points during a communication is not continuous. When a user sends or receives data or messages, the data or messages are divided into components known as packets. Every packet is treated as an independent unit of data.
In order to standardize the transmission between points over the Internet or the like networks, an OSI (Open Systems Interconnection) model was established. The OSI model separates the communications processes between two points in a network into seven stacked layers, with each layer adding its own set of functions. Each device handles a message so that there is a downward flow through each layer at a sending end point and an upward flow through the layers at a receiving end point. The programming and/or hardware that provides the seven layers of function is typically a combination of device operating systems, application software, TCP/IP and/or other transport and network protocols, and other software and hardware.
Typically, the top four layers are used when a message passes from or to a user and the bottom three layers are used when a message passes through a device (e.g., an IP host device). An IP host is any device on the network that is capable of transmitting and receiving IP packets, such as a server, a router or a workstation. Messages destined for some other host are not passed up to the upper layers but are forwarded to the other host. In the OSI and other similar models, IP is in Layer-3, the network layer.
Wireless Networks
Wireless networks can incorporate various types of mobile devices, such as, e.g., cellular and wireless telephones, PCs (personal computers), laptop computers, wearable computers, cordless phones, pagers, headsets, printers, PDAs, etc. For example, mobile devices may include digital systems to secure fast wireless transmissions of voice and/or data. Typical mobile devices include some or all of the following components: a transceiver (i.e., a transmitter and a receiver, including, e.g., a single chip transceiver with an integrated transmitter, receiver and, if desired, other functions); an antenna; a processor; one or more audio transducers (for example, a speaker or a microphone as in devices for audio communications); electromagnetic data storage (such as, e.g., ROM, RAM, digital data storage, etc., such as in devices where data processing is provided); memory; flash memory; a full chip set or integrated circuit; interfaces (such as, e.g., USB, CODEC, UART, PCM, etc.); and/or the like.
Wireless LANs (WLANs) in which a mobile user can connect to a local area network (LAN) through a wireless connection may be employed for wireless communications. Wireless communications can include, e.g., communications that propagate via electromagnetic waves, such as light, infrared, radio, microwave. There are a variety of WLAN standards that currently exist, such as, e.g., Bluetooth, IEEE 802.11, and HomeRF.
By way of example, Bluetooth products may be used to provide links between mobile computers, mobile phones, portable handheld devices, personal digital assistants (PDAs), and other mobile devices and connectivity to the Internet. Bluetooth is a computing and telecommunications industry specification that details how mobile devices can easily interconnect with each other and with non-mobile devices using a short-range wireless connection. Bluetooth creates a digital wireless protocol to address end-user problems arising from the proliferation of various mobile devices that need to keep data synchronized and consistent from one device to another, thereby allowing equipment from different vendors to work seamlessly together. Bluetooth devices may be named according to a common naming concept. For example, a Bluetooth device may possess a Bluetooth Device Name (BDN) or a name associated with a unique Bluetooth Device Address (BDA). Bluetooth devices may also participate in an Internet Protocol (IP) network. If a Bluetooth device functions on an IP network, it may be provided with an IP address and an IP (network) name. Thus, a Bluetooth Device configured to participate on an IP network may contain, e.g., a BDN, a BDA, an IP address and an IP name. The term “IP name” refers to a name corresponding to an IP address of an interface.
An IEEE standard, IEEE 802.11, specifies technologies for wireless LANs and devices. Using 802.11, wireless networking may be accomplished with each single base station supporting several devices. In some examples, devices may come pre-equipped with wireless hardware or a user may install a separate piece of hardware, such as a card, that may include an antenna. By way of example, devices used in 802.11 typically include three notable elements, whether or not the device is an access point (AP), a mobile station (STA), a bridge, a PCMCIA card or another device: a radio transceiver; an antenna; and a MAC (Media Access Control) layer that controls packet flow between points in a network.
In addition, Multiple Interface Devices (MIDs) may be utilized in some wireless networks. MIDs may contain two independent network interfaces, such as a Bluetooth interface and an 802.11 interface, thus allowing the MID to participate on two separate networks as well as to interface with Bluetooth devices. The MID may have an IP address and a common IP (network) name associated with the IP address.
Wireless network devices may include, but are not limited to Bluetooth devices, Multiple Interface Devices (MIDs), 802.11x devices (IEEE 802.11 devices including, e.g., 802.11a, 802.11b and 802.11g devices), HomeRF (Home Radio Frequency) devices, Wi-Fi (Wireless Fidelity) devices, GPRS (General Packet Radio Service) devices, 3G cellular devices, 2.5G cellular devices, GSM (Global System for Mobile Communications) devices, EDGE (Enhanced Data for GSM Evolution) devices, TDMA type (Time Division Multiple Access) devices, or CDMA type (Code Division Multiple Access) devices, including CDMA2000. Each network device may contain addresses of varying types including but not limited to an IP address, a Bluetooth Device Address, a Bluetooth Common Name, a Bluetooth IP address, a Bluetooth IP Common Name, an 802.11 IP Address, an 802.11 IP common Name, or an IEEE MAC address.
Wireless networks can also involve methods and protocols found in, e.g., Mobile IP (Internet Protocol) systems, in PCS systems, and in other mobile network systems. With respect to Mobile IP, this involves a standard communications protocol created by the Internet Engineering Task Force (IETF). With Mobile IP, mobile device users can move across networks while maintaining their IP Address assigned once. See Request for Comments (RFC) 3344. NB: RFCs are formal documents of the Internet Engineering Task Force (IETF). Mobile IP enhances Internet Protocol (IP) and adds means to forward Internet traffic to mobile devices when connecting outside their home network. Mobile IP assigns each mobile node a home address on its home network and a care-of-address (CoA) that identifies the current location of the device within a network and its subnets. When a device is moved to a different network, it receives a new care-of address. A mobility agent on the home network can associate each home address with its care-of address. The mobile node can send the home agent a binding update each time it changes its care-of address using, e.g., Internet Control Message Protocol (ICMP).
In basic IP routing (i.e. outside mobile IP), typically, routing mechanisms rely on the assumptions that each network node always has a constant attachment point to, e.g., the Internet and that each node's IP address identifies the network link it is attached to. In this document, the terminology “node” includes a connection point, which can include, e.g., a redistribution point or an end point for data transmissions, and which can recognize, process and/or forward communications to other nodes. For example, Internet routers can look at, e.g., an IP address prefix or the like identifying a device's network. Then, at a network level, routers can look at, e.g., a set of bits identifying a particular subnet. Then, at a subnet level, routers can look at, e.g., a set of bits identifying a particular device. With typical mobile IP communications, if a user disconnects a mobile device from, e.g., the Internet and tries to reconnect it at a new subnet, then the device has to be reconfigured with a new IP address, a proper netmask and a default router. Otherwise, routing protocols would not be able to deliver the packets properly.
Network and Information Discovery
In the evolution of wireless networking based on, e.g., wireless LAN (Local Area Network) and cellular technologies, and as mobility services prevail and people become increasingly mobile, it is increasingly important for a mobile device to be able to find an appropriate point of network attachment that meets the application requirements and the characteristics of the mobile, in a timely, accurate and efficient manner. By way of example, such network discovery can relate to, e.g., the discovery of information that the mobile station uses to access a network, such as, by way of example, a network attachment point identification (e.g., an L2 address and/or a geographical address of an access point), a MAC type (e.g., “IEEE 802.11g”) of an access point, a security type (e.g., “WPA” or “PANA and IPsec”) supported by an access point, a layer-3 type (e.g., “IPv4 only” or “IPv4/v6 dual stack”), a provider name, or the addresses of a server or an agent (e.g., PANA authentication agents, access routers, SIP servers and Mobile IP home agents).
Additionally, mobile users and their mobile devices (e.g., mobile phones, Personal Digital Assistants, notebook computers, on-vehicle networking devices and/or the like) need to discover a growing range of information as they travel across potentially heterogeneous radio networks. This information includes, e.g.:                User-interest information (i.e., information of interest to human users): Examples include the existence and/or locations, etc., of: a) local networks (such as, e.g., public hotspot networks and/or the like); b) network services (such as, e.g., voice-over-IP services and/or the like); c) networked devices (such as, e.g., printers, displays, disks and/or the like); d) applications and/or software utilities; e) location-sensitive information, application contents, dynamically changing information (such as, e.g., news information, local area information, information regarding traffic accidents and/or road conditions and/or the like) and/or the like, which are in the current and/or neighboring networks. In the preferred examples, a neighboring network includes a nearby network that a mobile device or user can move into (such as, e.g., a subsequent or next network from its current network). Depending on circumstances, a neighboring network's radio coverage area may or may not overlap with a radio coverage area of the mobile device's or user's current network.        Device-interest information: Emerging mobile devices often need information, which human users may or may not be interested in, regarding neighboring networks to better support mobility and mobile applications. For example, to reduce handoff delay and interruptions to on-going user applications during handoff, a mobile device can perform pre-handoff processing, before it starts the handoff into a target network. For example, a mobile device may acquire a local IP address from, and even authenticate with, the target network when the mobile is still using its current network to transport user application traffic even before the mobile detects the radio signals from the target network. To do so, the mobile device needs to know, e.g., the IP address of the IP address server (e.g., the Dynamic Host Configuration Protocol or DHCP server) and the authentication server in the target network before it starts handoff to the target network. See, e.g., device-interest information discussed in the above-referenced co-pending provisional applications entitled Network Discovery Mechanisms incorporated herein by reference above.        
In this document, mobile users and mobile devices may be referred to generally as “mobiles” in, e.g., contexts where there is no need to distinguish between a human user and a device.
Several frameworks and protocols are available for discovering network services and devices, which have been referred to as service discovery approaches. See, e.g., the below references [1], [2], [3] and [5], incorporated herein by reference. Examples of services include, by way of example: shared network devices such as, e.g., printers, displays and/or disks; software utilities; information such as, e.g., databases and files; and/or the like. The leading service discovery frameworks include Jini (see reference [1] below), (see reference UPnP [2] above), and Salutation (see reference [3] below).
These services were described in the above co-pending provisional applications entitled Network Discovery Mechanisms, incorporated herein by reference above and are discussed in the following paragraphs.
First, Jini allows devices and software components to form a dynamic distributed network system. It provides mechanisms for service construction, lookup, communication, and use in a distributed system. All services are registered with a central register. Clients locate services using a directory service referred to as the lookup service.
Second, Salutation provides a method for applications, services and devices to describe and advertise their capabilities, and to find other applications, services and devices. The Salutation architecture has two major components: Salutation Manager and Transport Manager. Salutation Manager is a service broker. Each service provider registers its capability with a Salutation Manager. A client queries a Solution Manager to find a service, and the Salutation Managers coordinate with each other to locate the service for the client. The Transport Manager provides reliable transport of Solution messages.
Third, the Universal Plug and Play (UPnP) is architecture for dynamically establishing peer-to-peer network connectivity among user devices. It provides capabilities for devices to dynamically join a network, obtain an IP address, convey its capabilities upon request, and learn about the presence and capabilities of other devices. UPnP does not use central service registry.
These existing service discovery mechanisms focus on discovering existing network services and devices. Among other deficiencies, they cannot support the discovery of dynamic information, such as changing traffic conditions, accidents, and/or other dynamically changing information. They allow a device to discover only other devices, services, or applications that implement the same service discovery platform. For example, an UPnP device may not be able to discover an IP router or a piece of network information or user content that is not implemented based on UPnP. Furthermore, existing service discovery methods do not support “neighborhood discovery”—e.g., discovering information regarding neighboring networks and location-based information, such as, e.g.: the existence and/or locations of neighboring networks; addresses of the DHCP servers, authentication servers, and SIP servers in a neighboring network; and/or other location-based network information and user content available in the neighboring networks.
Recently, an autonomous collaborative discovery approach was proposed by the present inventors, see item [6] below, to support real-time discovery of user and network information including location-sensitive information, dynamic information (e.g., traffic conditions), and neighboring networks (e.g., existence and locations of neighboring networks, and addresses of key network elements such as access routers and authentication servers in neighboring networks). In this approach, mobile users and their mobile devices act as scouts to collect user and network information as part of their routine use of each network. They then make the information available on a knowledge server, which can be independent of network providers, to be shared by all subscribing mobile users and devices of the knowledge server.
Recognizing that existing service discovery approaches lack the ability to support neighborhood discovery, the Internet Engineering Task Force (IETF) has been developing a Candidate Access Router Discovery (CARD) protocol (see reference [4] below) that allows user devices to discover the IP address and capabilities of access routers in neighboring networks. CARD, however, has a number of limitations, including:                It requires neighboring access routers to use the CARD protocol to dynamically exchange network information, which is difficult when neighboring networks belong to different network providers.        It requires all access routers to implement the CARD protocol to communicate with mobile users, which is a difficult proposition.        A mobile device can only obtain the information a local network provider configures its CARD protocol to provide. Thus, the available information can vary significantly from network to network. This is unsuitable to support mobile devices that may need different information depending on their different networking capabilities and user applications.        
Recently, peer-to-peer file sharing over the Internet has been growing rapidly. With reference to FIG. 1, existing peer-to-peer file sharing mechanisms can be classified into the following categories, depending on the techniques used in discovering the files:                Approaches using centralized index server clusters: These approaches use centralized index server clusters to maintain up-to-date indexes that indicate which end devices have which popular files. When a user wants a file, it first queries an index server to find out which peers may have the requested file. Then, the user can go to the peers directly to get the file. By way of example, this type of method is used by the popular music file sharing system Napster (see, e.g., references [10], [11] and [12] below).        Approaches using no index: These approaches do not maintain any index. Instead, they rely on flooding for a user to find the files that the user wants. For example, Gnutella ((see, e.g., references [10], [11] and [12] below) is a peer-to-peer file sharing system using such methods. When a user wants a file, the user sends a request to all of its neighbors. Each neighbor will, in turn, forward the request to its own neighbors. Each node with the requested file sends the file to the request originator. The scope of the search is typically controlled by the number of hops that the request can be forwarded.        Approaches using local indexes: Each user maintains its local index pointing to the locations of frequently requested files. For example, Freenet (see, e.g., references [10] and [11] below) is a file sharing system that uses local indexes. When a node receives a request for a file, it searches its local index first to see if it knows where the requested file is located. If it knows the locations, it forwards the request to only those locations. This reduces the query traffic volume over the networks.        
Existing peer-to-peer file sharing methods are not designed for sharing information in a highly time-sensitive manner (such as, e.g., information about neighboring networks), which is important for mobile users/devices, especially for in-vehicle networking devices (e.g., networking devices fixedly mounted within a vehicle, such as, e.g., related to navigation and/or information systems and/or other systems). Furthermore, they are not designed for network neighborhood discovery.
The preferred embodiments improve upon technologies described, e.g., in the following information, each of which is incorporated herein by reference in its entirety:
[1] Sun Microsystems Inc., sun.com/jini/;
[2] Microsoft Corporation, “Universal Plug and Play Device Architecture”, upnp.org/;
[3] Salutation Consortium, “Salutation Architecture Specification”, Jun. 1, 1999, salutation.org/;
[4] Marco Liebsch and Ajoy Singh (editors), “Candidate Access Router Discovery”, Internet Draft draft-ietf-seamoby-card-protocol-06.txt, Internet Engineering Task Force, June 2004;
[5] K. Arabshian, H. Schulzrinne, “GloServ: Global Service Discovery Architecture”, Mobiquitous 2004, Boston;
[6] T. Zhang, S. Madhani, E. van den Berg, “AC-CDS Autonomous Collaborative Collection, Discovery, and Sharing of User and Network Information”, International Conference on Information Technology: Research and Education (ITRE), Hsinchu Taiwan, Jun. 28, 2005;
[7] Resource Description Framework, w3.org/TR/rdf-primer;
[8] SOAP, Simple Object Access Protocol, w3.org/TR/soap12;
[9] P. Flajolet, D. Gardy, L. Thimonier, “Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-Organizing Search”, Discrete Applied Mathematics 39, pp. 207-229, 1992;
[10] A. Creapo, H. Garcia-Molina, “Routing Indices for Peer-to-Peer Systems;”
[11] A. Saroiu, P. K. Gummadi, S. D. Gribble, “A Measurement Study of Peer-to-Peer Sharing Systems;”
[12] napster.com;
[13] gnutella.wego.com;
[14] freetnet.sourceforge.com.